//爬楼梯
class Solution {
public:
    int climbStairs(int n) {
        int val = 0;
        vector<int> dp(n+1);
        //状态表示：到达i位置的方法数
        //状态转移方程：dp[i] = dp[i-1] + dp[i-2];
        //初始化：dp[1] = 1 , dp[2] = 2;
        if(n == 1) return 1;
        else if(n == 2) return 2;
        dp[1] = 1;
        dp[2] = 2;
        for(size_t i = 3 ; i <= n ; ++i)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

//斐波那契数列
class Solution {
public:
    int fib(int n) {
        vector<int> dp(n+1);
        if(n == 0) return 0;
        else if(n == 1) return 1;
        dp[0] = 0 , dp[1] = 1;
        for(size_t i = 2 ; i <= n ; ++i)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

//打家劫舍
class Solution {
public:
    int rob(vector<int>& nums) {
        //状态表示：以i屋子为结尾的能偷的最大金额
        //状态转移方程：dp[i] = max(dp[i-2]+nums[i] , dp[i-1]);
        //初始化：dp[0] = nums[0] , dp[1] = nums[1]
        int n = nums.size();
        if(n == 1) return nums[0];
        else if(n == 2) return max(nums[0],nums[1]);
        vector<int> dp(n);
        dp[0] = nums[0] , dp[1] = nums[1] , dp[2] = dp[0] + nums[2];
        for(size_t i = 3 ; i < n ; ++i)
        {
            dp[i] = max(dp[i-2],dp[i-3])+nums[i];
        }
        int ret = max(dp[n-1],dp[n-2]);
        return ret;
    }
};

//不同路径
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        dp[0][1] = 1;
        for(size_t i = 1 ; i <= m ; ++i)
        {
            for(size_t j = 1 ; j <= n ; ++j)
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};

//最小路径和
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //状态表示：到达i、j位置的最小和
        //状态转移方程：dp[i][j] = min(dp[i-1][j] , dp[i][j-1])+grid[i][j];
        int m = grid.size() , n = grid[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0x3f3f3f3f));
        for(size_t i = 1 ; i <= m ; ++i)
        {
            for(size_t j = 1 ; j <= n ; ++j)
            {
                int val = min(dp[i-1][j],dp[i][j-1]);
                if(val == 0x3f3f3f3f) val = 0;
                dp[i][j] = val + grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};

//三角形最小路径和
class Solution {
public:
    const int DE_VAL = 0x3f3f3f3f;
    int minimumTotal(vector<vector<int>>& triangle) {
        int m = triangle.size() , n = triangle[m-1].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,DE_VAL));
        for(size_t i = 1 ; i <= m ; ++i)
        {
            for(size_t j = 1 ; j <= triangle[i-1].size() ; ++j)
            {
                int temp = min(dp[i-1][j-1],dp[i-1][j]);
                if(temp == DE_VAL) temp = 0;
                dp[i][j] = temp + triangle[i-1][j-1];
            }
        }
        int ret = DE_VAL;
        for(auto& x : dp[m])
        {
            if(x < ret) ret = x;
        }
        return ret;
    }
};

//回文子串
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int ret = 0;
        vector<vector<bool>> dp(n,vector<bool>(n));
        for(int i = n-1 ; i >= 0 ; --i)
        {
            for(size_t j = i ; j < n ; ++j)
            {
                if(s[i] != s[j]) dp[i][j] = false;
                else
                {
                    if(i == j) dp[i][j] = true;
                    else if(i + 1 == j) dp[i][j] = true;
                    else dp[i][j] = dp[i+1][j-1] == true ? true : false;
                }
                if(dp[i][j])
                {
                    ret++;
                }
            }
        }
        return ret;
    }
};